#include <stdio.h>
#include "Item.h"
#include "PQ.h"

void PQsort(Item a[], int l, int r);

int main(int argc, char *argv[]){
    Item a[] = {'A', 'S', 'O', 'R', 'T', 'I', 'N', 'G',
                'E', 'X', 'A', 'M', 'P', 'L', 'E'};

    int i;

    for (i = 0; i < 16; i++) {
        printf("%c ", a[i]);
    }
    printf("\n");

    PQsort(a, 0, 14);

    for (i = 0; i < 16; i++) {
        printf("%c ", a[i]);
    }
    printf("\n");
    return 0;
}

/** 
 * Program 9.6 Sorting with a priority queue
 * -------------------------------------------
 * To sort a subarray `a[l..r]` using a priority-queue ADT,
 * we simply use `PQinsert` to put all the elements on the priority queue, and
 * then use `PQdelmax` to remove them, in decreasing order.
 * This sorting algorithm runs in time proportional to $N \lg N$, but
 * uses extra space proportional to the number of items to be sorted (for the priority queue).
 */
void PQsort(Item a[], int l, int r){
    PQinit(r-l+1);
    int k;

    for (k = l; k<=r; k++) {
        PQinsert(a[k]);
    }

    for (k = r; k >=l; k--) {
        a[k] = PQdelmax();
    }
}